/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-01-30 21:46:40
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-02 22:17:59
 * @FilePath: \LeetCode\560.和为-k-的子数组.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=560 lang=cpp
 *
 * [560] 和为 K 的子数组
 *
 * 方法1：暴力子串匹配 O(n^2)
 *
 * 方法2：使用 hash 表记录所有前缀子数组的和
 * - 两前缀和之差为 k
 * 
 * 官方题解：hash 表添加记录 hash[0] = 1 优化去除 if (sub_sum == k)
 */

#include <vector>
#include <unordered_map>
#include <iostream>

// @lc code=start
class Solution
{
public:
    int subarraySum(const std::vector<int> &nums, int k)
    {
        int count = 0;

        int sub_sum = 0;
        /* key:前缀子数组的和 value:出现次数 */
        std::unordered_map<int, int> perfix_sum;
        perfix_sum[0] = 1;  // sub_sum == k 的情况
        for (auto n : nums)
        {
            sub_sum += n;
            /* 两前缀和之差为 k */
            auto it = perfix_sum.find(sub_sum - k);
            if (it != perfix_sum.end())
                count += it->second;

            perfix_sum[sub_sum]++;
        }

        return count;
    }
};
// @lc code=end

int main(void)
{
    Solution solution;
    std::vector<int> nums = {1, 1, 1, 0};

    std::cout << solution.subarraySum(nums, 2) << std::endl;

    return 0;
}